By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 28, Issue 1, pp. 1-381

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums

Haripriyan Hampapuram and Michael L. Fredman

pp. 1-9

BibTeX  Abstract Full Text:  PDF

Dynamic 2-Connectivity with Backtracking

Johannes A. La Poutré and Jeffery Westbrook

pp. 10-26

BibTeX  Abstract Full Text:  PDF

On the Structure of $\cal NP_\Bbb C$

Gregorio Malajovich and Klaus Meer

pp. 27-35

BibTeX  Abstract Full Text:  PDF

Weighted NP Optimization Problems: Logical Definability and Approximation Properties

Marius Zimand

pp. 36-56

BibTeX  Abstract Full Text:  PDF

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Tomás Feder and Moshe Y. Vardi

pp. 57-104

BibTeX  Abstract Full Text:  PDF

Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems

Thomas H. Cormen, Thomas Sundquist, and Leonard F. Wisniewski

pp. 105-136

BibTeX  Abstract Full Text:  PDF

L-Printable Sets

Lance Fortnow, Judy Goldsmith, Matthew A. Levy, and Stephen Mahaney

pp. 137-151

BibTeX  Abstract Full Text:  PDF

The Inverse Satisfiability Problem

Dimitris Kavvadias and Martha Sideri

pp. 152-163

BibTeX  Abstract Full Text:  PDF

On Syntactic versus Computational Views of Approximability

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani

pp. 164-191

BibTeX  Abstract Full Text:  PDF

Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms

Stefan Felsner and Lorenz Wernisch

pp. 192-209

BibTeX  Abstract Full Text:  PDF

Fast Algorithms for Constructing t-Spanners and Paths with Stretch t

Edith Cohen

pp. 210-236

BibTeX  Abstract Full Text:  PDF

Smart SMART Bounds for Weighted Response Time Scheduling

Uwe Schwiegelshohn, Walter Ludwig, Joel L. Wolf, John Turek, and Philip S. Yu

pp. 237-253

BibTeX  Abstract Full Text:  PDF

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen

Baruch Awerbuch, Yossi Azar, Avrim Blum, and Santosh Vempala

pp. 254-262

BibTeX  Abstract Full Text:  PDF

Near-Linear Time Construction of Sparse Neighborhood Covers

Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg

pp. 263-277

BibTeX  Abstract Full Text:  PDF

Unoriented $Theta$-Maxima in the Plane: Complexity and Algorithms

David Avis, Bryan Beresford-Smith, Luc Devroye, Hossam Elgindy, Eric Guévremont, Ferran Hurtado, and Binhai Zhu

pp. 278-296

BibTeX  Abstract Full Text:  PDF

A Spectral Algorithm for Seriation and the Consecutive Ones Problem

Jonathan E. Atkins, Erik G. Boman, and Bruce Hendrickson

pp. 297-310

BibTeX  Abstract Full Text:  PDF

New Collapse Consequences of NP Having Small Circuits

Johannes Köbler and Osamu Watanabe

pp. 311-324

BibTeX  Abstract Full Text:  PDF

Sublogarithmic Bounds on Space and Reversals

Viliam Geffert, Carlo Mereghetti, and Giovanni Pighizzini

pp. 325-340

BibTeX  Abstract Full Text:  PDF

Separator-Based Sparsification II: Edge and Vertex Connectivity

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer

pp. 341-381

BibTeX  Abstract Full Text:  PDF